package com.lsa.edmonds.chap8;

import java.util.List;

import com.lsa.helpers.CollectionUtils;
import com.lsa.helpers.IntArrayListAdapter;
import com.lsa.shenn.common.InsertionSort;
import com.lsa.shenn.common.Sorter;
import com.lsa.helpers.SubListAdapter;

public class MergeSort implements Sorter
{
	private static int SIMPLE_SORT_SIZE = 3;
	private Sorter sorter = new InsertionSort();

	public int[] sort(int[] array)
	{
		sort(IntArrayListAdapter.adapt(array));
		return array;
	}

	public List<Integer> sort(List<Integer> array)
	{	
		sort(array, 0, array.size() - 1);
		return array;
	}
	
	void sort(List<Integer> array, int from, int to)
	{
		if (to - from + 1< SIMPLE_SORT_SIZE)
		{
			sorter.sort(SubListAdapter.adapt(array, from, to));
			return;
		}
		
		int half = (from + to) / 2;
		sort(array, from, half - 1 );
		sort(array, half , to);
		
		List<Integer> list = CollectionUtils.mergeAsc(SubListAdapter.adapt(array, from, half - 1),
				SubListAdapter.adapt(array, half, to));
		
		for (int i = 0; i < list.size(); i++)
		{
			array.set(from + i, list.get(i));
		}
	}

}
